package kaiao.dynamic;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class 单词拆分 {

	public static void main(String[] args) {

	}

	/**
	 * 根据题意找到前驱状态
	 * 本质上跟硬币问题是一样的，都是通过coin去找，本质上是被整除的问题，与前一个已知答案的数对比是否能被coin整除
	 *
	 * @author kai.ao
	 * @since 2024/6/17
	 */
	public boolean wordBreak(String s, List<String> wordDict) {

        // 初始化动态数组
		int n = s.length();
		boolean[] dp = new boolean[n + 1];
		dp[0] = true;

		// 将字典转化为Set更方便使用 主要是set的contains比list快
		Set<String> dict = new HashSet<>(wordDict);

		// i为字符的长度设置 j为往前推的字符数量
		for (int i = 1; i < n + 1; i++) {

			for (int j = 1; j < i + 1 && !dp[i]; j++) {
				String sub = s.substring(j - 1, i);

				// 判断当前数组减去某个长度后得到的列表的值
				if (dict.contains(sub)) dp[i] = dp[j - 1];
			}
		}

		return dp[n];
	}
}
